package effizienz;
import java.util.Scanner;

public class MaxSumme{
  public static void main(String[] args){
    Scanner eingabe=new Scanner(System.in);
    int anz=Integer.parseInt(args[0]);
    int[] z=new int[anz];
    for(int i=0; i<anz; i++)
      z[i]=eingabe.nextInt();
    int m;
    long t0=System.nanoTime();
    m=maxsumme1(z);
    long t1=System.nanoTime();
    m=maxsumme2(z);
    long t2=System.nanoTime();
    m=maxsumme3(z);
    long t3=System.nanoTime();
    System.out.println(m);
    System.out.println(t1-t0);
    System.out.println(t2-t1);
    System.out.println(t3-t2);
  }

  public static int maxsumme3(int[] z){
    int s, max=0, n=z.length;
    for(int i=0; i<n; i++)
      for(int j=i; j<n; j++){
        s=0;
        for(int k=i; k<=j; k++)
          s+=z[k];  // Befehl B
        if(s>max) max=s;
      }
    return max;
  }

  public static int maxsumme2(int[] z){
    int s, max=0, n=z.length;
    for(int i=0; i<n; i++){
      s=0;
      for(int j=i; j<n; j++){
        s+=z[j];
        if(s>max) max=s;
      }
    }
    return max;
  }

  public static int maxsumme1(int[] z){
    int max=0, endmax=0, n=z.length;
    for(int i=0; i<n; i++){
      endmax+=z[i];
      if(endmax<0) endmax=0;
      if(endmax>max) max=endmax;
    }
    return max;
  }
}
